1. Field of the Invention
This invention relates to improvements in computer systems and methods for operating computer systems, and more particularly to improvements in computer systems of the type which use reference counts in the operation and management of the associated computer memory, and still more particularly to improvements in methods and apparatuses for managing the reference counts of a computer system with which the invention is associated.
2. Description of the Prior Art
The development of computer storage or memory management systems has a long history with many related branches of research. Many memory structures are shown by H. M. Deitel, An Introduction to Operating Systems, Addison-Wesley, Mass., Chapter 7, 1982. Other major issues of interest are discussed by Knuth, D., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968, and Cohen, J. "Garbage Collection of Linked Structures," Computing Surveys, Vol. 13, No. 3, September, 1981, pp. 341-367.
Becoming of interest with the rapid development in the areas of artificial intelligence is the development of so-called "knowledge bases", large data bases, for use, for instance, in containing extremely large or complex information stores requiring dynamic organization. See, for example, Suwa, M., et al, "Knowledge Base Mechanisms", Preliminary Report on Fifth Generation Computer Systems, ICOT, 1980. Examples of some large data bases under consideration or implemented include, for instance, data bases which contain legal information, such as verbatim case reports, medical information for use in diagnosing possible diseases which present particular symptoms, certain patent information including abstracts, claims, and so forth. In such data bases, it is often desirable to search through sometimes millions of words and characters, then identify a particular record (case, patent, diagnosis, etc.) related to the words and characters.
Typical memory systems with which the invention can be used (although not to which the invention is limited) can be seen in copending patent applications by Oxley et al, entitled "COMPUTER MEMORY SYSTEM", Ser. No. 630,476, filed July 12, 1984 and by Thatte el al, entitled COMPUTER SYSTEM ENABLING AUTOMATIC MEMORY OPERATIONS, Ser. No. 630,478, filed July 12, 1984, both applications being assigned to the assignee hereof and incorporated herein by reference. Portions of a patent application of Oxley et al., entitled COMPUTER MEMORY SYSTEM WITH PARALLEL GARBAGE COLLECTION INDEPENDENT FROM AN ASSOCIATED USER PROCESSOR, Ser. No. 636,187, filed July 31, 1984, assigned to the assignee hereof described reference count objectives and purposes to which the present invention particularly pertains.
The memory system of said copending applications respond to conditions, equations or instructions from a user CPU to allocate memory blocks and allow the user CPU to execute certain instructions with regard to the allocated memory blocks. The memory system also is garbage collected in accordance with certain design parameters. The memory system operation is based upon the use of binding registers which interface the user CPU to the memory, which enables the memory to be seen by the user CPU as a block oriented memory, and which permits the memory management unit to control memory overhead functions. Despite the actual or hardware configuration of the memory system, it has an apparent logical memory organization, as seen by the user CPU. (The logical memory organization is referred to as a "logical address space", as distinguished from a "virtual address space" which is a memory representation or abstraction as seen by the memory management unit, and from a physical memory, which is the actual physical memory elements of the memory system.) The binding registers serve as a window or portal into and out of the logical memory system. Through use of the binding registers, the user processor can be directly addressing only a limited number of blocks at any instant.
The user CPU uses a set of individual binding registers as a base for referencing some value within a previously bound block. The manner by which the user CPU addresses the binding registers can be, for example, by specifying a particular binding register. Memory operations in a computer system (aside from data writes and retrievals) can be viewed as a series of events which, among other things, create and destroy pointers. For each event, certain information is provided which determines whether a pointer is either created or destroyed. In computers of the type of interest herein, a count is maintained as a part of the operation of the computer of the number of pointers which reference blocks of memory which have been allocated or defined. This count is referred to herein as the "reference count". Thus, the action of creating or destroying a pointer also results in a reference count of the computer memory system being either incremented or decremented. The combination of several such events, one after another in a temporal sense, is referred to herein as a "reference stream".
The phenomenon of referencing (creating a pointer to) a block and then, relatively quickly, dereferencing (destroying) the same pointer sometimes occurs quite frequently, for example, when "CDRing" down a list or when there is a call to a procedure followed by a return from the procedure. Each reference and dereference to the same block can be called a "systematic" reference/dereference pair, and the associated necessary action to the reference count of the block can be called a systematic increment/decrement pair. (Pairs of this type are of primary interest herein, as distinguished from accidentally created pairs.)
Updating a block's reference count takes processor time, and performance can be especially degraded when the block whose reference count needs to be updated is not in the main memory of the computer system. Use of valuable processor time and degradation of performance is especially wasteful when it involves the increment of a reference count which is decremented soon thereafter, as would occur, for instance, in an increment/decrement pair as described above.